The roots of modern cryptography arose from the widespread availability of radio in wartime in the early part of the twentieth century. Specifically, modern cryptography extends beyond the early Spartan practice of using a scytale in wartime, a transposition ciphering tool. In modern times, given the mediums employed to send messages, interception and decoding problems must be addressed by the cryptographer. Modern day communications call for both privacy, such as by encryption of the message, and assurance of the source of the message. In fact it is paramount in modern day communications that we trust the source of information or communication.
SFE is a technique that enables mutually distrustful parties to evaluate a function on their inputs, such that, while the result is computed, the inputs remain private. Depending on the function, SFE may involve significant computational costs. SFE has become practical for many secure transaction applications due to the increase in computation and communication resources currently available for communication to both individuals and businesses. Types of transactions that can occur using SFE for security can include, for example, auctions, contract signing and distributed database mining to name a few.
Currently the use of SFE is limited due to the high costs of computation associated with the use of SFE algorithms.
Thus far, SFE has been accomplished using a variety of algorithms, including, for example, the Garbled Circuit (GC) algorithm, also known as Yao's Garbled Circuit. A server, such as P1, encrypts or garbles a computed function F represented by a Boolean circuit C, which can be blindly evaluated gate by gate. The results of C are sent directly to another server, such as P2. P2 then evaluates the GC under encryption, obtains the encrypted output of the GC and sends the encrypted output directly back to P1. Server P1 decrypts the output received from P2, and sends the decrypted output directly back to P2.
The GC can be constructed by P1 choosing two secrets for each wire of a circuit C he needs to garble. For each gate Gi, P1 creates and sends to P2 a garbled table Ti. Each garbled table created has the following property: given a set of garblings for the set of input wires of the corresponding gate, each table Ti generated based on the Gi allows to compute only the garbling of the corresponding output value. That is, P2 can only recover a single garbled output of each gate Gi from the table Ti and the garblings of the Gi's inputs. The tables Ti are usually implemented as a set of encryptions, where each pair of input garblings forming Gi serves as a key to the encryption of the corresponding output garbling Ti.
FIG. 1 is an example of a known, prior art GC, where, for an AND gate, T0 is represented by the following table:
      T    0    =      {                                                      t              00                        =                                          Enc                                  w                  1                  0                                            ⁡                              (                                                      Enc                                          w                      2                      0                                                        ⁡                                      (                                          w                      0                      0                                        )                                                  )                                                                                                    t              01                        =                                          Enc                                  w                  1                  0                                            ⁡                              (                                                      Enc                                          w                      2                      1                                                        ⁡                                      (                                          w                      0                      0                                        )                                                  )                                                                                                    t              10                        =                                          Enc                                  w                  1                  1                                            ⁡                              (                                                      Enc                                          w                      2                      0                                                        ⁡                                      (                                          w                      0                      0                                        )                                                  )                                                                                                    t              11                        =                                          Enc                                  w                  1                  1                                            ⁡                              (                                                      Enc                                          w                      2                      1                                                        ⁡                                      (                                          w                      0                      1                                        )                                                  )                                                        
The table T0 is received by P2 directly from P1; Further, e.g., given the input garblings w_1^0 and w_2^0, P2 attempts to decrypt each row of the table and recovers the encrypted output W0 of G0. Only one decryption will succeed from the decryption of the table T0, and will reveal the output wire secret W0. P2 then proceeds evaluating the entire garbled circuit as above, and eventually obtains the garbling of the output wire W. P2 then sends the garbling to P1 for decryption. P1 can decrypt the output and send directly back to P2. P2 never learns the values of the input or internal wires.
The biggest drawback of using garbled circuit technology in SFE is the complexity associated with generating and computing garbled circuits by processors, such as servers, and transferring the input garblings. Evaluation of garbled circuits is linear in the size of the circuit, and requires on average four AES calls per gate. Further, circuit construction can require up to eight AES calls per gate. Communication between the servers consists primarily of sending garbled tables Ti (four AES encryptions per each gate). Finally, transferring input garblings requires a small number (two or three) of public-key operations per input transferred.
Transfer of the garbled Circuit can be a costly communication expense for large functions. Additionally, computation of the garbled circuit, especially if done in bulk by the server for many clients, results in significant computational cost.
The complexity associated with using garbled circuit operations can be reduced by introducing a tamper-proof computing device (token) into the system. The token can be configured to generate the garbled circuit. Then, a first processor, such as server P1 does not have to generate and transmit the garbled circuit to a second processor, such as server P2. Instead, the server P1 can generate the token T and send it to server P2. T then generates and transmits the garbled circuit, where token T is synchronized with server P1. The synchronization of T with P1 can be achieved by embedding a secret key k in token T by server P1. Then, during the (execution of SFE), server P2 chooses an element x from the domain of the embedded in T pseudorandom function generator (PRFG) function F. Then T based on the randomness generates GC and outputs it to P2. This eliminates computation costs and complexity at the processor P1, encrypts the signal, but does not ensure that T is a trusted source for the information and can be trusted by P2.
Given this type of circuit, ie., a garbled circuit generated by a token T of the first processor P1, the second processor P2 may want to be protected from the misbehavior (or cheating) of the token T, i.e. incorrect generation of the GC.
One known way to protect P2 from T cheating is to have P1, or it's agent T, send more than one message to P2. For example, T could send 2 messages to P2. P2 chooses one message to be live and asks P1 to reveal the randomness used construction of all the other messages to see if the other messages are constructed properly. The probability that the live message was constructed properly is ½ in the case of 2 messages.